package com.yjc.dp;

import java.util.Arrays;

/**
 * 1668. 最大重复子字符串
 *
 * @author yjc
 * @create 2024-07-18 15:12
 */
public class Subject_2 {
    public static void main(String[] args) {
        String sequence = "aaabaaaabaaabaaaabaaaabaaaabaaaaba";
        String word = "aaaba";

        int m = word.length();
        int n = sequence.length();

        if (n < m) {
            System.out.println(0);
            return;
        }

        int[] dp = new int[n];//保存每个位置 word 的最大连续重复次数
        for (int i = m - 1; i < n; i++) {
            boolean valid = true;

            for (int j = 0; j < m; j++) {
                if (sequence.charAt(i - m + j + 1) != word.charAt(j)) {
                    valid = false;
                    break;
                }
            }
            if (valid) dp[i] = (i == m - 1 ? 0 : dp[i - m]) + 1;

        }
        int res = Arrays.stream(dp).max().getAsInt();
        System.out.println(res);

    }
}
